package Two_Pointers;

import java.util.Arrays;

//双指针专题
public class t16 {
    //16. 最接近的三数之和  中等
    public static void main(String[] args) {
        int nums[] = {0,1,3};
        int target =4;
        System.out.println(threeSumClosest(nums, target));
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        int left = 0;
        int len = nums.length;
        //int right = nums.length - 1;
        //int k = left + 1;
        int sum = Integer.MAX_VALUE;
        while (left < len) {
            int right = len-1;
            int k = left+1;
            //k = left+1;
            while (k<right){
                int tmp = nums[left] + nums[k] + nums[right];
                sum = Math.abs(tmp-target)>Math.abs(sum-target)?sum:tmp;
                if(sum==target){
                    return sum;
                }
                if(tmp-target>0){
                    int t = nums[right];
                    right--;
                    while (t==nums[right]&&right>k){
                        right--;
                    }
                }
                if(tmp-target<0){
                    int t = nums[k];
                    k++;
                    while (t==nums[k]&&right>k){
                        k++;
                    }
                }
            }
            left++;
        }
        return sum;
    }

    //超时
    public static int threeSumClosest1(int[] nums, int target) {
        //Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        int sum = Integer.MAX_VALUE;
        int left = 0;
        int right = nums.length - 1;
        int k = left + 1;
        while (left < right) {
            while (k < right) {
                int tmp = nums[left] + nums[right] + nums[k];

                sum = Math.abs(sum - target) > Math.abs(tmp - target) ? tmp : sum;
                if (sum == target) {
                    return sum;
                }
                k++;
            }
            left++;
            k = left + 1;
            if (k == right) {
                left = 0;
                right--;
                k = 1;
            }
        }
        return sum;
    }
}
